package binaryfind

// findLastLE 查找最后一个小于等于给定值的元素
func findLastLE(slice []int, value int) (result int) {

	start := 0
	end := len(slice) - 1

	for start <= end {

		mid := start + ((end - start) >> 1)
		// 若当前元素小于等于给定值
		if slice[mid] <= value {
			// 当前元素是最后一个，当前元素就是目标值。当前元素的后置元素大于给定值，当前元素就是目标元素
			if mid == len(slice)-1 || slice[mid+1] > value {
				return mid
			}
			// 目标元素在右侧
			start = mid + 1
		} else {
			// 目标在左侧
			end = mid - 1
		}

	}

	return -1
}

// findFirstGE 查找第一个大于等于给定值的元素
func findFirstGE(slice []int, value int) (result int) {

	start := 0
	end := len(slice) - 1
	for start <= end {
		mid := start + ((end - start) >> 1)
		// 目标在左侧
		if slice[mid] >= value {
			// 左侧已没有元素，当前节点就是目标。前置节点小于当前元素，当前节点就是目标
			if mid == 0 || slice[mid-1] < value {
				return mid
			}
			// 目标在左侧
			end = mid - 1
		} else {
			// 目标在右侧
			start = mid + 1
		}
	}

	return -1
}

// findLast 查找最后一个值的坐标
func findLast(slice []int, value int) (result int) {

	start := 0
	end := len(slice) - 1

	for start <= end {
		mid := start + ((end - start) >> 1)
		if slice[mid] == value {
			// 就是当前值
			if mid == len(slice)-1 || slice[mid+1] != value {
				return mid
			}
			// 目标值在右侧
			start = mid + 1
		} else if slice[mid] > value {
			// 目标在左侧
			end = mid - 1
		} else {
			// 目标在右侧
			start = mid + 1
		}
	}

	return -1
}

// findFirst 查找第一个等于该值的元素
func findFirst(slice []int, value int) (result int) {

	start := 0
	end := len(slice) - 1

	for start <= end {
		mid := start + ((end - start) >> 1)
		if slice[mid] == value {
			// 就是当前值
			if mid == 0 || slice[mid-1] != value {
				return mid
			}
			// 目标值在左侧
			end = mid - 1
		} else if slice[mid] > value {
			// 目标在左侧
			end = mid - 1
		} else {
			// 目标在右侧
			start = mid + 1
		}
	}

	return -1
}

// findWithLoop 循环方式实现二分查找
func findWithLoop(slice []int, value int) (result int) {

	start := 0
	end := len(slice) - 1
	for start <= end {
		mid := start + ((end - start) >> 1)
		if slice[mid] == value {
			return mid
		} else if slice[mid] > value {
			end = mid - 1
		} else {
			start = mid + 1
		}
	}
	return -1
}

// findWithRecursion 递归方式实现二分查找
func findWithRecursion(slice []int, value int) (result int) {

	return findWithRange(slice, 0, len(slice)-1, value)
}

// findWithRange 查询指定范围的
func findWithRange(slice []int, start int, end int, value int) (result int) {

	if start > end {
		return -1
	}
	mid := start + ((end - start) >> 1)
	if slice[mid] == value {
		return mid
	} else if slice[mid] > value {
		return findWithRange(slice, start, mid-1, value)
	} else {
		return findWithRange(slice, mid+1, end, value)
	}

}

// squareRoot 求平方根
func squareRoot(value float64) (result float64) {

	// 要精确到小数点后 n 位 就是逐位求取，先从整数位开始
	// 平方根的整数部分取值得范围 为 0 ～ (value/2)+1
	// 1. 求整数部分
	target := float64(0)
	end := value/2 + 1
	step := float64(1)
	for square := target * target; target <= end; square = target * target {

		if step < 0.000001 {
			break
		}
		if square == value {
			return target
		} else if square > value {
			target = target - step
			step = step / 10
		} else {
			// 这里用折半查找性能更好
			target += step
		}
	}

	return target
}
